//
// Created by Lenovo on 2023/3/8.
//

/* 洛谷 P1168 */
/* 对顶堆 */

//模拟 STL 都过了，tm 时间不够，老子真是吐了
//我写的是对的qwq，十万个数据都过了啊

#include <stdio.h>
#include <stdlib.h>
#define Max(A, B) ((A) > (B) ? (A) : (B))
#define Min(A, B) ((A) < (B) ? (A) : (B))

typedef int ElemType;

typedef struct Tree
{
    ElemType data;
    struct Tree *pLeft, *pRight, *pParent;//双亲结点，便于交换
} Tree;

void up(Tree *tree, int n)
{
    Tree *tmpT = tree;
    if (!n) //小根堆
    {
        while (tmpT -> pParent != NULL && tmpT -> data < tmpT -> pParent -> data)
        {
            int tmp = tmpT -> data;
            tmpT -> data = tmpT -> pParent -> data;
            tmpT -> pParent -> data = tmp;
            tmpT = tmpT -> pParent;
        }
    }
    else //大根堆
    {
        while (tmpT -> pParent != NULL && tmpT -> data > tmpT -> pParent -> data)
        {
            int tmp = tmpT -> data;
            tmpT -> data = tmpT -> pParent -> data;
            tmpT -> pParent -> data = tmp;
            tmpT = tmpT -> pParent;
        }
    }
}

void down(Tree *tree, int n) // 0 代表小根堆，1 代表大根堆
{
    if (!n)
    {
        Tree *tmpT = tree;
        while (tmpT -> pLeft != NULL || tmpT -> pRight != NULL)
        {
            if (tmpT -> pLeft != NULL && tmpT -> pRight != NULL)
            {
                int min = Min(tmpT -> pLeft -> data, tmpT -> pRight -> data);
                if (tmpT -> data > min)
                {
                    int tmp = tmpT -> data;
                    tmpT -> data = min;
                    if (tmpT -> pLeft -> data < tmpT -> pRight -> data)
                    {
                        tmpT -> pLeft -> data = tmp;
                        tmpT = tmpT -> pLeft;
                    }
                    else
                    {
                        tmpT -> pRight -> data = tmp;
                        tmpT = tmpT -> pRight;
                    }
                }
                else
                {
                    break;
                }
            }
            else if (tmpT -> pLeft != NULL && tmpT -> pRight == NULL)
            {
                if (tmpT -> data > tmpT -> pLeft -> data)
                {
                    int tmp = tmpT -> data;
                    tmpT -> data = tmpT -> pLeft -> data;
                    tmpT -> pLeft -> data = tmp;
                    tmpT = tmpT -> pLeft;
                }
                else
                {
                    break;
                }
            }
            else
            {
                if (tmpT -> data > tmpT -> pRight -> data)
                {
                    int tmp = tmpT -> data;
                    tmpT -> data = tmpT -> pRight -> data;
                    tmpT -> pRight -> data = tmp;
                    tmpT = tmpT -> pRight;
                }
                else
                {
                    break;
                }
            }
        }
    }
    else
    {
        Tree *tmpT = tree;
        while (tmpT -> pLeft != NULL || tmpT -> pRight != NULL)
        {
            if (tmpT -> pLeft != NULL && tmpT -> pRight != NULL)
            {
                int max = Max(tmpT -> pLeft -> data, tmpT -> pRight -> data);
                if (tmpT -> data < max)
                {
                    int tmp = tmpT -> data;
                    tmpT -> data = max;
                    if (tmpT -> pLeft -> data > tmpT -> pRight -> data)
                    {
                        tmpT -> pLeft -> data = tmp;
                        tmpT = tmpT -> pLeft;
                    }
                    else
                    {
                        tmpT -> pRight -> data = tmp;
                        tmpT = tmpT -> pRight;
                    }
                }
                else
                {
                    break;
                }
            }
            else if (tmpT -> pLeft != NULL && tmpT -> pRight == NULL)
            {
                if (tmpT -> data < tmpT -> pLeft -> data)
                {
                    int tmp = tmpT -> data;
                    tmpT -> data = tmpT -> pLeft -> data;
                    tmpT -> pLeft -> data = tmp;
                    tmpT = tmpT -> pLeft;
                }
                else
                {
                    break;
                }
            }
            else
            {
                if (tmpT -> data < tmpT -> pRight -> data)
                {
                    int tmp = tmpT -> data;
                    tmpT -> data = tmpT -> pRight -> data;
                    tmpT -> pRight -> data = tmp;
                    tmpT = tmpT -> pRight;
                }
                else
                {
                    break;
                }
            }
        }
    }
}

Tree *insert(Tree *parent, int num, Tree *tree, int n) //返回新的双亲节点地址，n 为 1 表示大根堆
{
    Tree *new = (Tree *) malloc(sizeof(Tree));
    new -> pLeft = NULL;
    new -> pRight = NULL;
    if (parent -> pLeft == NULL)
    {
        parent -> pLeft = new;
        new -> data = num;
        new -> pParent = parent;
        up(new, n);
        return parent;
    }
    else if (parent -> pRight == NULL)
    {
        parent -> pRight = new;
        new -> data = num;
        new -> pParent = parent;
        up(new, n);
        return parent;
    }
    else
    {
        Tree *tmp = tree;
        while (tmp -> pLeft != NULL)
        {
            tmp = tmp -> pLeft;
        }
        tmp -> pLeft = new;
        new -> data = num;
        new -> pParent = tmp;
        up(new, n);
        return tmp;
    }
}

void Swap(Tree *top, Tree *new)
{
    int tmp = top -> data;
    top -> data = new -> data;
    new -> data = tmp;
}


int main()
{
    int n;
    scanf("%d", &n);
    int arr[n];
    for (int i = 0; i < n; i++)
    {
        scanf("%d", &arr[i]);
    }

    Tree *bigTree = (Tree *) malloc(sizeof(Tree)), *smallTree = (Tree *) malloc(sizeof(Tree));
    bigTree -> pParent = NULL, smallTree -> pParent = NULL;
    bigTree -> pLeft = NULL, bigTree -> pRight = NULL;
    smallTree -> pLeft = NULL, smallTree -> pRight = NULL;

    int numSmall = 0;//记录两个树的节点个数
    Tree *bigTmp = bigTree, *smallTmp = smallTree;//记录双亲节点
    bigTree -> data = -123456789;
    for (int i = 0; i < n; i++) //打印次数
    {
        if (!i) // i == 0 时给小根堆堆顶赋值
        {
            smallTree -> data = arr[i];
            numSmall++;
        }
        if (arr[i] >= smallTree -> data && i != 0) //数据大于小根堆堆顶(临时中位数)，插入小根堆
        {
            smallTmp = insert(smallTmp, arr[i], smallTree, 0); //树，数字，双亲节点地址  完成后更改双亲节点
            numSmall++;
        }
        else if (arr[i] < smallTree -> data)
        {
            if (bigTree -> data == -123456789)
            {
                bigTree -> data = arr[i];
            }
            else
            {
                bigTmp = insert(bigTmp, arr[i], bigTree, 1);
            }
        }
        //判断小根堆元素个数是否符合要求
        int k = i / 2 + 1;//判断小根堆的元素个数的标准数
        if (numSmall > k)
        {
            // 1.小根堆堆顶值插入大根堆
            if (bigTree -> data == -123456789)
            {
                bigTree -> data = smallTree -> data;
            }
            else
            {
                Tree *ret = insert(bigTmp, smallTree -> data, bigTree, 1);
                // 2.维护大根堆
                up(ret -> pLeft, 1);
            }
            // 3.删除小根堆根节点并维护
            Swap(smallTree, smallTmp -> pLeft);
            free(smallTmp -> pLeft);
            smallTmp -> pLeft = NULL;
            down(smallTree, 0);
            numSmall--;
        }
        else if (numSmall < k)
        {
            Tree *ret = insert(smallTmp, bigTree -> data, smallTree, 0);
            numSmall++;
            up(ret -> pLeft, 0);
            Swap(bigTree, bigTmp -> pLeft);
            free(bigTmp -> pLeft);
            bigTmp -> pLeft = NULL;
            down(bigTree, 1);
        }

        if (!(i % 2))
        {
            printf("%d\n", smallTree -> data);
        }
    }

    system("pause");
    return 0;
}